\n The user interface is similar to the cumulative constraint, with a \n list of task start times, durations and resources; and a maximum \n resource limit. There is one extra argument, a cost function which \n is to be minimised. \n
\n Probing for scheduling differs radically from the cumulative constraint\n because it includes a search routine. In its behaviour it is an\n optimisation procedure and not simply a constraint which enforces \n consistency. \n
\n The search is focussed towards an optimal vlaue of the cost function.\n
\n ")). :- comment(eg, "\n% Example program: simple schedule optimisation\n\n:- lib(probing_for_scheduling).\n:- lib(fd).\n\nex1([X,Y,Z],Cost) :-\n [OldX,OldY,OldZ]=[1,5,5],\n Durations=[10,5,5],\n Resources=[1,2,1],\n MaxResource=2,\n NewStarts=[X,Y,Z],\n fd:(NewStarts::1..10),\n CostFun= abs(X-OldX) + abs(Y-OldY) + abs(Z-OldZ),\n\tprobe_sched(NewStarts,Durations,Resources,MaxResource,CostFun),\n\tCost is CostFun.\n\nex2([X,Y,Z],Cost) :-\n [OldX,OldY,OldZ]=[1,5,5],\n Durations=[10,5,5],\n Resources=[1,2,1],\n MaxResource=2,\n NewStarts=[X,Y,Z],\n fd:(NewStarts::1..10),\n Constraints=[\n XDiff >= X-OldX, XDiff >= OldX-X,\n YDiff >= Y-OldY, YDiff >= OldY-Y,\n\t\t ZDiff >= Z-OldZ, ZDiff >= OldZ-Z,\n\t\t Cost =:= XDiff+YDiff+ZDiff\n ],\n Options=[granularity(1),priority(5)],\n\tprobe_cstr_sched(NewStarts,Durations,Resources,MaxResource,\n Constraints,Cost,Options).\n\nex3(Starts,MaxResource,Cost) :-\n\tStarts=[S1,S2,S3,S4],\n\tfd:(S1::1..10),\n\tfd:(S2::3..10),\n\tfd:(S3::1..5),\n\tfd:(S4::3..10),\n [D1,D2,D3,D4]=[5,5,3,3],\n Durations=[D1,D2,D3,D4],\n\tResources=[1,1,1,1],\n\tCostFun= maxlist([S1+D1,S2+D2,S3+D3,S4+D4]),\n\tprobe_sched(Starts,Durations,Resources,MaxResource,CostFun),\n\tCost is CostFun.\n \n"). :- comment(fun_to_cons_var / 3, [summary : "Convert a cost expression to a variable and a list of constraints, \nsuitable to pass into probe_cstr_sched/7", amode : fun_to_cons_var(+, -, -), args : ["CostFun" : "a cost function of the form accepted by probe_sched/5", "ConsList" : " a variable which will be instantiated to a list of constraints, \nsuitable to pass into probe_cstr_sched/7", "CostVar" : "a variable constrained to take a value greater than or equal to \nthe cost function"], resat : no, see_also : [probe_sched / 5, probe_cstr_sched / 7], desc : html("\nIf the user needs to use probe_cstr_sched instead of probe_sched, this predicate can be used to convert the cost function to a list of constraints and a cost variable suitable for passing to probe_cstr_sched\n"), eg : "\nfun_to_cons_var(abs(X-10)+abs(Y-3),ConsList,Var)\n"]). :- comment(maxlist / 2, [summary : "Find the maximum of a list of numeric expressions", amode : maxlist(++, ?), args : ["List" : " a list of (n) integer-valued expressions", "Maximum" : "The maximum"], resat : no, see_also : [probe_sched / 5], desc : html("
\nExporting 'maxlist' ensures that the syntax of the cost function for probe_sched\ncan also be handled by 'is', thus enabling:\n
\n?- probe_sched(S,D,R,M,CostFun), Cost is CostFun\n\t\n"), eg : "\nX is maxlist([2,3*7-20,4-1])\n"]). :- comment(probe_cstr_sched / 7, [summary : "Find a resource-feasible schedule that minimises the\ncost, subject to the constraints", amode : probe_cstr_sched(+, +, +, ++, +, -, ++), args : ["Starts" : " A list of (n) task start times (integers or\nfinite domain variables)", "Durations" : "A list of (n) task durations (integers or\nfinite domain variables)", "Resources" : "A list of (n) task resource needs (integers)", "MaxResource" : "The available resource, not to be exceeded", "Constraints" : "A list of numeric equations and inequations, \nusing functors '=:=', '>=', '>', '=<' and '<'.", "Cost" : "A numeric variable which will be minimised during search", "Options" : " A list, '[granularity(G),priority(P)]',\n where\n 'G' is an integer specifying the time granularity, and\n 'P' is the priority of the probe demon."], resat : no, see_also : [probe_sched / 5, min_max / 2, set_up_probe / 5, make_overlap_bivs / 5, probe_search / 5], desc : html("
\nThis offers the same functionality as probe_sched/5, but with added \nflexibility, and a more complex user interface. The extra arguments offer \nthe user more control. \n
\nThe Cost argument is a variable, and it must be linked to the task \nvariables by the list of linear constraints. The user can add not only \nlinear constraints on the cost function, but also constraints between the \ntask variables. Only constraints made explicit in this list are 'seen' by \nthe probe. probe_cstr_sched also posts them to the fd solver.\n
\nThe options offer user control over\nthe temporal granularity, and the priority of the probe.\n
\nThe algorithm uses min_max, but directs the search using a probe\nwhich focusses the search on the optimum. The probe is a procedure\nthat finds optimal solutions to a relaxed problem ignoring resource\nlimits. For details see setup_probe. Additionally the algorithm\nsets up a binary variable between each pair of tasks, see\nmake_overlap_bivs. Whenever the probe returns tentative start\ntimes, these are propagated to the overlap binary variables yielding a\ntotal resource usage which reveals any bottlenecks, where needed\nresources exceed thos available. probe_search then\nnon-deterministically introduces a new constraint which reduces the\nbottleneck.\nThe probe_sched call:\n
\nprobe_sched(Ss,Ds,Rs,MaxR,abs(X-X1)+Y)\n\ntranslates into the probe_cstr_sched call:\n
\nprobe_cstr_sched(Ss,Ds,Rs,MaxR,[Cost=:=E1+Y,E1>=X-X1,E1>=X1-X],Cost,\n[granularity(1),priority(5)])\n\nThus making the default granularity '1' and the default priority '5'.\n")]). :- comment(probe_sched / 5, [summary : "Find a resource-feasible schedule that minimises the\ncost function", amode : probe_sched(+, +, +, ++, ?), args : ["Starts" : " a list of (n) task start times (integers or\nfinite domain variables)", "Durations" : "a list of (n) task durations (integers or\nfinite domain variables)", "Resources" : "a list of (n) task resource needs (integers or \nfinite domain variables)", "MaxResource" : "The available resource, not to be exceeded", "CostFun" : "An expression involving start times and durations\nto be minimised"], resat : no, see_also : [probe_cstr_sched / 7, min_max / 2, set_up_probe / 5, make_overlap_bivs / 5, probe_search / 5, maxlist / 2], desc : html("
\n\tThis predicate finds start times for a set of tasks, which\nminimise the value of a given cost function.\n
\nThe cost function is the only information the search algorithm can use to\nfocus on the optimum. It cannot guide the search if the cost is a variable, \nonly linked to the tasks start times by constraints. For this reason the \ncost function admits the special functions abs and maxlist.\n
\nThe syntax for cost functions is:\n
\nCostFunction ::- PosExpr | PosExpr + PosExpr | Integer * PosExpr\nPosExpr ::- abs(LinearExpr) | maxlist([LinearExpr]) | LinearExpr.\n\n
\nThe algorithm is described in more detail in the documentation of \nprobe_cstr_sched/7. \n
\n"), eg : "\nprobe_schedule(Starts,CostFun) :-\n\tStarts=[X,Y,Z],\n fd:(Starts::1..10),\n Durations=[10,5,5],\n Resources=[R1,R2,R3],\n fd:(R1::1..2), R2=2, R3=1,\n MaxResource=2,\n [OldX,OldY,OldZ]=[1,5,5],\n CostFun= abs(X-OldX)+abs(Y-OldY)+abs(Z-OldZ),\n\tprobe_sched(Starts,Durations,Resources,MaxResource,CostFun).\n"]).